package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 字母大小写全排列
 */

public class Code784 {
    public static void main(String[] args) {
        String s = "a1b2";
        System.out.println(new Code784().letterCasePermutation(s));
    }

    public List<String> letterCasePermutation(String s) {
        char[] chars = s.toCharArray();
        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backtrace(chars, 0, sb, ans);
        return ans;
    }

    private void backtrace(char[] chars, int index, StringBuilder sb, List<String> ans) {
        if (index == chars.length) {
            ans.add(sb.toString());
            return;
        }

        if (Character.isAlphabetic(chars[index])) {
            sb.append(Character.toLowerCase(chars[index]));
            backtrace(chars, index + 1, sb, ans);
            sb.deleteCharAt(sb.length() - 1);
            sb.append(Character.toUpperCase(chars[index]));
        } else {
            sb.append(chars[index]);
        }
        backtrace(chars, index + 1, sb, ans);
        sb.deleteCharAt(sb.length() - 1);
    }
}
